In the early days of network security development, Bell Labs developed a system they dubbed Greyer, a model based loosely on the Blacker Front End[BFE, Mund87] but which was much less secure. Greyer could be employed for both providing end-to-end encryption between a pair of hosts communicating over an insecure network, and for providing network-level encryption between a pair of gateways, each of which is protecting a group of naive hosts.
Many improvements in both networks and encryption of network communications have been developed since the introduction of Greyer. Modern day network cryptography involves improving security and efficiency while reducing computation costs. Concepts suitable for stronger assumption algorithms often differ from, and cannot be translated to weaker assumption algorithms, which are more secure encryption systems. The development of encryption models for private communications on public networks has been an area of great interest and development, as the need to provide readily accessible secure communication and transactions has grown tremendously due to improvements in communication channels.
Specifically, two-party general secure function evaluation (SFE) enables two parties to evaluate any function on their respective inputs x and y, while maintaining privacy of both x and y. Efficient SFE algorithms are suitable for performing a variety of electronic transactions, previously impossible due to mutual mistrust of participants. SFE is useful for transactions such as, for example, auctions, contract signing, distributed database mining, etc. As computation and communication resources have increased dramatically, SFE has become truly practical for securely performing private interactions on public networks.
Currently, there are several existing implementations of full-fledged, generic two-party SFE with malicious players. This clearly demonstrates the feasibility and efficiency of SFE for many useful functions, represented as circuits of up to ≈106 gates. Today, generic SFE is a relatively developed technology, and improvements that reduce costs, improve efficiency, and/or improve security by even incremental factors are welcomed among cryptographers and engineers.
General SFE has been a subject of immense amount of research. The work of Andrew C. Yao. in “Protocols for secure computations”, Proc. 23rd IEEE Symp. on Foundations of Comp. Science, pages 160-164, Chicago, 1982. IEEE.), for example, has resulted in significant advances in the field. Further, an example of a full practical implementation of general SFE based on garbled circuits is discussed, for example, by Lindell et al. in “Implementing Two-Party Computation Efficiently with Security Against Malicious Adversaries”, SCN '08: Proceedings of the 6th international conference on Security and Cryptography for Networks, pages 2-20. Springer-Verlag, 2008.
A recent work, Lindell et al. proposes one of the more efficient protocols for providing security with Yao's protocol against malicious adversaries. The encryption proposed by Lindell et al is suitable for use in a Random Oracle Model (ROM) version, a relatively strong assumption.
In the Lindell protocol, a circuit constructor party $P—1$P1 first assigns random keys $k_i^j in {0,1}^n$kijε{0,1}n to each wire value. Next, for the $i$i-th wire $W_i$Wi, $P—1$P1 chooses a random permutation $pi_i$πi of ${0,1}${0,1}. Wire encoding is then achieved for pair $w_i^j=(k_i^j, c_i^j)$wij=(kij,cij), where $c_i^j=Pi_i(j)$cij=Πi(j). For gate $G_g$Gg, the gate table consists of four entries indexed by the values of $c_i^j$cij and is given by: begin{equation*}c—1,c—2:Enc—{k—1^{b—1},k—2^{b—2}}^{g∥c—1∥c—2}(k—3^{G(b—1,b—2}∥c—3),
end{equation*}
      c    1    ,            c      2        ⁢          :        ⁢                  ⁢                  Enc                              k            1                          b              1                                ,                      k            2                          b              2                                                g          ⁢                                                c              1                                            ⁢                      c            2                              (                                    k            3                          G              ⁡                              (                                                      b                    1                                    ,                                      b                    2                                                  )                                              ⁢                                                c              3                        )                          ,            
where $k—1$k1 and $k—2$k2 are the keys on the gate's input wires, $k—3$k3 is the key on the gate output wire, $b—1=pi—1^{−1}(c—1), b—2=pi—2^{−1}(c—2)$b1=π1−1(c1),b2=π2−1(c2), and $c—3=pi—3(G(b—1,b—2)$c3=π3(G(b1,b2). The encryption function $Enc_{k—1,k—2}^s(m)$Enck1,k28(m) is computed as follows:
1. $k leftarrow KDF (k—1∥s, |m|)$k←KDF(k1∥s,|m|);
2. $k′ leftarrow KDF (k—2∥s, |m|)$k′←KDF(k2∥s,|m|);
3. $e leftarrow m oplus k oplus k′$e←m⊕k⊕k′; and
4. return $e$e.
Here, KDF (Key Derivation Function) is a pseudorandom function, such as Advanced Encryption Standard (AES) or keyed hash function. Thus, creation of each table entry involves two KDF executions.
Similarly, decryption of a table entry involves an inverse of the above encryption operations:
1. k←KDF(k1∥s, |e|);
2. k′←KDF(k2∥s, |e|);
3. e←m⊕k⊕k′; and
4. return m.
Decryption of the table entry involves two KDF invocations as well.
Although good efficiency is achieved in the ROM version applying the Lindell et al protocol, a double encryption is still required for the Non-ROM, more secure version.
The Lindell protocol does not apply to systems of weaker assumptions. This is due to the fact that one cannot encrypt, e.g., as follows: e=m⊕KDF(k1∥k2∥s, |m|), since part of the key is known to the adversary, security of pseudorandom functions cannot be analyzed. For example, in Garbled Circuit (GC) evaluation, the evaluator $P—2$P2 will know $k—1$k1 and $k—2$k2, allowing him to decrypt the corresponding entry in the garbled table. However, two other keys in the garbled table are encrypted in part by $k—1$k1 or $k—2$k2. As such, even though they are also encrypted with a key that is partially unpredictable to $P—2$P2, Pseudo-Random Function Generator (PRFG) properties do not allow the assertion of claims of secrecy of the other encryptions in the garbled table.
Currently what is known for garbled circuits with weaker assumptions is that each entry in the garbled table is an encryption of an encryption of the target value. Each of the two encryptions is under the corresponding wire key. As a result, decryption of the circuit results in two decryption operations for each gate of a given circuit.